package com.wm.algorithm.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName: SimpleBinaryTree
 * @Description: 简单级别
 * @Author: Deamer
 * @Date: 2022/5/17 23:07
 **/
public class SimpleBinaryTree {

    /**
     * 剑指 Offer 68 - II. 二叉树的最近公共祖先
     * https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
     * 方法：回溯+前、后序位置
     * 思路：递归在前序位置寻找目标值，后序位置判断两个目标节点不为空即找到LCA节点
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(n)
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        return find2(root, p.val, q.val);
    }

    private TreeNode find2(TreeNode node, int val1, int val2) {
        if (node == null) {
            return null;
        }
        // 前序位置寻找到目标节点
        if (node.val == val1 || node.val == val2) {
            return node;
        }
        TreeNode left = find2(node.left, val1, val2);
        TreeNode right = find2(node.right, val1, val2);
        // 后序位置判断两个目标节点非空即寻找到LCA
        if (left != null && right != null) {
            return node;
        }
        return left == null ? right : left;
    }

    /**
     * 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
     * https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
     * 方法2：迭代
     * 思路：LCA是位于左右目标节点之间的。根据这个前提条件，祖先节点比左右目标值节点的值都大，说明LCA在当前节点的左侧；
     * 祖先节点比左右目标值节点的值都小，说明LCA在当前节点的右侧
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(1)
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (ancestor.val > p.val && ancestor.val > q.val) { // LCA在ancestor左侧
                ancestor = ancestor.left;
            } else if (ancestor.val < p.val && ancestor.val < q.val) { // LCA在ancestor右侧
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }

    /**
     * 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
     * https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
     * 方法1：回溯+前、后续位置
     * 思路：回溯在左右子树中找到各自的目标值，这个目标值是在前序位置判断得到，LCA是在后序位置找到，即当中左右子节点都不为空的情况。
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    // O(n)/O(n)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p.val, q.val);

    }

    private TreeNode find(TreeNode root, int val1, int val2) {
        if (root == null) {
            return null;
        }
        if (root.val == val1 || root.val == val2) {
            return root;
        }
        TreeNode left = find(root.left, val1, val2);
        TreeNode right = find(root.right, val1, val2);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }


    /**
     * 700. 二叉搜索树中的搜索
     * https://leetcode.cn/problems/search-in-a-binary-search-tree/
     * 方法：迭代+二分查找的思想
     * 思路：利用BST的左小右大的特性，判断查找的值在左子树还是在右子树，每次减少一半数量的节点做判断
     *
     * @param root
     * @param val
     * @return
     */
    // 时间复杂度O(n)：其中n是二叉搜索树的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要递归n次。
    // 空间复杂度O(1)：没有使用额外的空间。
    public TreeNode searchBST2(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                return root;
            }
            root = root.val > val ? root.left : root.right;
        }
        return null;
    }

    /**
     * 700. 二叉搜索树中的搜索
     * https://leetcode.cn/problems/search-in-a-binary-search-tree/
     * 方法：递归+二分查找的思想
     * 思路：利用BST的左小右大的特性，判断查找的值在左子树还是在右子树，每次减少一半数量的节点做判断
     *
     * @param root
     * @param val
     * @return
     */
    // 时间复杂度O(n)：其中n是二叉搜索树的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要递归n次。
    // 空间复杂度O(n)：最坏情况下递归需要 O(N) 的栈空间。
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val > val) {
            return searchBST(root.left, val);
        } else if (root.val < val) {
            return searchBST(root.right, val);
        }
        return root;
    }

    /**
     * 226. 翻转二叉树
     * https://leetcode.cn/problems/invert-binary-tree/
     * 方法2：分解法(递归)
     *
     * @param root
     * @return
     */
    // O(n)/O(n)
    // 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
    public TreeNode invertTree2(TreeNode root) {
        if (root == null) {
            return root;
        }
        // 利用函数定义，先翻转左右子树
        TreeNode leftTree = invertTree2(root.left);
        TreeNode rightTree = invertTree2(root.right);
        // 然后交换左右子节点
        root.left = rightTree;
        root.right = leftTree;
        // 定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
        return root;
    }

    /**
     * 226. 翻转二叉树
     * https://leetcode.cn/problems/invert-binary-tree/
     * 方法1：遍历+前(中、后)序位置
     *
     * @param root
     * @return
     */
    // O(n)/O(n)
    public TreeNode invertTree(TreeNode root) {
        traverse4(root);
        return root;
    }

    private void traverse4(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序位置
        // 每一个节点需要做的事就是交换它的左右子节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        // 遍历框架，去遍历左右子树的节点
        invertTree(root.left);
        invertTree(root.right);
    }

    /**
     * 993. 二叉树的堂兄弟节点
     * https://leetcode.cn/problems/cousins-in-binary-tree/?show=1
     * 方法：遍历+利用前序位置
     * 思路：遍历找到x,y的深度和父节点即可
     */
    TreeNode parentX = null;
    TreeNode parentY = null;
    int deptX = 0, deptY = 0;
    int x, y;

    // O(n)/O(n)
    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        traverse(root, 0, null);
        if (deptX == deptY && parentX != parentY) {
            // 判断 x，y 是否是表兄弟节点
            return true;
        }
        return false;
    }

    // 遍历寻找x,y
    private void traverse(TreeNode root, int dept, TreeNode parent) {
        if (root == null) {
            return;
        }
        // 前序位置记录当前深度和父节点
        if (root.val == x) {
            // 找到 x，记录它的深度和父节点
            deptX = dept;
            parentX = parent;
        }
        if (root.val == y) {
            // 找到 y，记录它的深度和父节点
            deptY = dept;
            parentY = parent;
        }
        traverse(root.left, dept + 1, root);
        traverse(root.right, dept + 1, root);
    }

    /**
     * 563. 二叉树的坡度
     * https://leetcode.cn/problems/binary-tree-tilt/?show=1
     * 方法：利用后序位置
     * 思路：在寻找二叉树的所有元素和的后续位置处理坡度
     *
     * @param root
     * @return
     */
    int res3 = 0;

    // O(n)二叉树中结点总数。我们需要遍历每一个结点/O(n) 递归时我们需要存储 n 个结点
    public int findTilt(TreeNode root) {
        sum(root);
        return res3;
    }

    // 定义：输入一棵二叉树，返回这棵二叉树所有元素的和
    private int sum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSumNum = sum(node.left);
        int rightSumNum = sum(node.right);
        // 后续位置
        res3 += Math.abs(leftSumNum - rightSumNum);
        return leftSumNum + rightSumNum + node.val;
    }


    // 层序遍历结果集合
    List<List<Integer>> result = new ArrayList<>();

    /**
     * 层序遍历（借鉴思路）
     * 思路：采用递归，自顶向下，像递归遍历单链表的函数，把二叉树的每一层抽象理解成单链表的一个节点进行遍历。
     * 存储当前节点值的同时保存下一层的节点集合
     *
     * @param root
     */
    // O(n)/O(n)
    public void leftTraverse3(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        levelTraverse2(nodes);

    }

    private void levelTraverse2(List<TreeNode> curLevelNodes) {
        if (curLevelNodes.isEmpty()) {
            return;
        }
        // 前序位置，计算当前层的值和下一层的节点列表
        List<Integer> nodeValues = new ArrayList<>();
        List<TreeNode> nextLevelNodes = new ArrayList<>();
        for (TreeNode node : curLevelNodes) {
            nodeValues.add(node.val);
            if (node.left != null) {
                nextLevelNodes.add(node.left);
            }
            if (node.right != null) {
                nextLevelNodes.add(node.right);
            }
        }
        // 前序位置添加结果，可以得到自顶向下的层序遍历
        result.add(nodeValues);
        levelTraverse2(nextLevelNodes);
        // 后序位置添加结果，可以得到自底向上的层序遍历结果
        // result.add(nodeValues);
    }

    /**
     * 层序遍历（借鉴思路）
     * 思路：采用递归，按照前序遍历，遍历到某层就取出某层的集合，将当前节点加进去
     * 这个解法更像是从左到右的「列序遍历」，而不是自顶向下的「层序遍历」，其本质还是二叉树的前序遍历，只不过得到的是层序遍历的结果
     *
     * @param root
     */
    // O(n)/O(n)
    public void leftTraverse2(TreeNode root) {
        if (root == null) {
            return;
        }
        // root 视为第 0 层
        levelTraverse(root, 0);
    }

    private void levelTraverse(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // 前序位置，看看是否已经存储 depth 层的节点了
        if (result.size() <= depth) {
            // 第一次进入 depth 层
            result.add(new ArrayList<>());
        }
        // 前序位置，在 depth 层添加 root 节点的值
        result.get(depth).add(root.val);
        levelTraverse(root.left, depth + 1);
        levelTraverse(root.right, depth + 1);
    }

    /**
     * 层序遍历（推荐）
     * 思路：自定向下，每层自左向右遍历，使用队列保存每一层的节点，在取某层的某个节点的时候，同时要保存这个节点下的左右子节点。
     *
     * @param root
     */
    // O(n)/O(n)
    public void leftTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 从上到下遍历二叉树的每一层
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            // 从左到右遍历每一层的每个节点
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                System.out.println(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

    /**
     * 543. 二叉树的直径
     * https://leetcode.cn/problems/diameter-of-binary-tree/
     * 方法：后序位置
     * 思路：每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。
     * 由于后序位置知道左右子树的信息
     * 把计算「直径」的逻辑放在后序位置，准确说应该是放在 maxDepth 的后序位置，因为 maxDepth 的后序位置是知道左右子树的最大深度的。
     *
     * @param root
     * @return
     */
    // O(n)/O(n)
    int maxDiameter2 = 0;// 计算最大直径的长度

    public int diameterOfBinaryTree2(TreeNode root) {
        maxDepth4(root);
        return maxDiameter2;
    }

    private int maxDepth4(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth3(root.left);
        int rightMax = maxDepth3(root.right);
        // 后序位置，顺便计算最大直径
        int myDiameter = leftMax + rightMax;
        // 更新全局最大直径
        maxDiameter2 = Math.max(maxDiameter, myDiameter);
        return 1 + Math.max(leftMax, rightMax);
    }

    /**
     * 543. 二叉树的直径
     * https://leetcode.cn/problems/diameter-of-binary-tree/
     * 方法：前序位置(不推荐)
     * 思路：每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。
     * 遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求和算出最大值即可。
     *
     * @param root
     * @return
     */
    // O(n^2)/O(n)
    int maxDiameter = 0;// 计算最大直径的长度

    public int diameterOfBinaryTree(TreeNode root) {
        traverse3(root);
        return maxDiameter;
    }

    /**
     * 遍历二叉树
     *
     * @param root
     */
    private void traverse3(TreeNode root) {
        if (root == null) {
            return;
        }
        // 对每个节点计算直径
        int leftMax = maxDepth3(root.left);
        int rightMax = maxDepth3(root.right);
        int myDiameter = leftMax + rightMax;
        // 更新全局最大直径
        maxDiameter = Math.max(maxDiameter, myDiameter);
        traverse3(root.left);
        traverse3(root.right);
    }

    // 计算二叉树的最大深度
    private int maxDepth3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth3(root.left);
        int rightMax = maxDepth3(root.right);
        return 1 + Math.max(leftMax, rightMax);
    }

    /**
     * 144. 二叉树的前序遍历
     * 方法二：分解法
     * 思路：一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果
     * 递归函数，充分利用这个函数的返回值
     *
     * @param root
     * @return
     */
    // 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
    // 最坏时间复杂度会达到 O(N^2)   /O(n)
    public List<Integer> preorderTraverse(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        // 前序遍历的结果，root.val 在第一个
        res.add(root.val);
        // 利用函数定义，后面接着左子树的前序遍历结果
        res.addAll(preorderTraverse(root.left));
        // 利用函数定义，最后接着右子树的前序遍历结果
        res.addAll(preorderTraverse(root.right));
        return res;
    }

    /**
     * 144. 二叉树的前序遍历
     * 方法一：一次遍历
     * 思路：traverse函数配合外部变量
     *
     * @param root
     * @return
     */
    // 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
    // 最坏时间复杂度会达到 O(N)   /O(n)
    List<Integer> res2 = new LinkedList<>();

    // 返回前序遍历结果
    public List<Integer> preorderTraverse2(TreeNode root) {
        traverse2(root);
        return res2;
    }

    // 二叉树遍历函数
    public void traverse2(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序位置
        res2.add(root.val);
        traverse2(root.left);
        traverse2(root.right);
    }


    /**
     * 104. 二叉树的最大深度
     * https://leetcode.cn/problems/maximum-depth-of-binary-tree/
     * 方法二：分解问题---对应动态规划核心框架
     * 思路：首先利用递归函数的定义算出左右子树的最大深度，然后推出原树的最大深度，主要逻辑自然放在后序位置。
     */
    // O(n)/O(n) n:二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度。
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 利用定义，计算左右子树的最大深度
        int leftMax = maxDepth2(root.left);
        int rightMax = maxDepth2(root.right);
        // 整棵树的最大深度等于左右子树的最大深度取最大值，然后再加上根节点自己
        return Math.max(leftMax, rightMax) + 1;
    }


    /**
     * 104. 二叉树的最大深度
     * https://leetcode.cn/problems/maximum-depth-of-binary-tree/
     * 方法一：一次遍历二叉树---对应回溯法核心框架
     * 思路：遍历一遍二叉树，用一个外部变量记录每个节点所在的深度，取最大值就可以得到最大深度。
     *
     * @param root
     * @return
     */
    // 记录最大深度
    int res;
    // 深度变量，可理解为一个游走在二叉树上的指针
    int dept;

    // 主函数
    public int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    // 二叉树遍历框架
    // O(n)/O(n) n:二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度。
    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序位置
        dept++;
        if (root.left == null && root.right == null) {
            // 到达叶子节点，更新最大深度
            res = Math.max(res, dept);
        }
        traverse(root.left);
        traverse(root.right);
        // 后序位置
        dept--;
    }
}


